{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge In Between Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mergeInBetween"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并两个链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个链表&nbsp;<code>list1</code> 和&nbsp;<code>list2</code>&nbsp;，它们包含的元素分别为&nbsp;<code>n</code> 个和&nbsp;<code>m</code> 个。</p>\n",
    "\n",
    "<p>请你将&nbsp;<code>list1</code>&nbsp;中下标从 <code>a</code> 到 <code>b</code> 的全部节点都删除，并将<code>list2</code>&nbsp;接在被删除节点的位置。</p>\n",
    "\n",
    "<p>下图中蓝色边和节点展示了操作后的结果：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/28/fig1.png\" style=\"height: 130px; width: 504px;\" />\n",
    "<p>请你返回结果链表的头指针。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/28/merge_linked_list_ex1.png\" style=\"width: 406px; height: 140px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]\n",
    "<b>输出：</b>[0,1,2,1000000,1000001,1000002,5]\n",
    "<b>解释：</b>我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/28/merge_linked_list_ex2.png\" style=\"width: 463px; height: 140px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]\n",
    "<b>输出：</b>[0,1,1000000,1000001,1000002,1000003,1000004,6]\n",
    "<b>解释：</b>上图中蓝色的边和节点为答案链表。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= list1.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= a &lt;= b &lt; list1.length - 1</code></li>\n",
    "\t<li><code>1 &lt;= list2.length &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-in-between-linked-lists](https://leetcode.cn/problems/merge-in-between-linked-lists/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-in-between-linked-lists](https://leetcode.cn/problems/merge-in-between-linked-lists/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3,4,5]\\n3\\n4\\n[1000000,1000001,1000002]', '[0,1,2,3,4,5,6]\\n2\\n5\\n[1000000,1000001,1000002,1000003,1000004]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        tmp = list2\n",
    "        b_end = tmp\n",
    "        while tmp!=None:\n",
    "            if tmp.next!=None:\n",
    "                b_end = tmp.next\n",
    "            tmp = tmp.next\n",
    "        index = 0\n",
    "        res = None\n",
    "        if a == 0:\n",
    "            res = list2\n",
    "        else:\n",
    "            res = list1\n",
    "        tmp = list1\n",
    "        while tmp!=None:\n",
    "            if index+1 == a:\n",
    "                k = tmp.next\n",
    "                tmp.next = list2\n",
    "                tmp = k\n",
    "                index += 1 \n",
    "                continue\n",
    "            if index == b:\n",
    "                b_end.next = tmp.next\n",
    "            tmp = tmp.next\n",
    "            index += 1\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        start = ListNode(0)\n",
    "        t0 = start\n",
    "        start.next = list1\n",
    "        #实例1： 先找到2（t0）\n",
    "        save_a = a\n",
    "        while(a):\n",
    "            t0 = t0.next\n",
    "            a -= 1\n",
    "        #print(t0.val)\n",
    "        t1 = t0\n",
    "        b = b - save_a + 2\n",
    "        #print(b)\n",
    "        while(b):\n",
    "            t1 = t1.next\n",
    "            b -= 1\n",
    "        #print(t1.val)\n",
    "        #插入\n",
    "        t0.next = list2\n",
    "        #list2的最后一个\n",
    "        while(list2.next):\n",
    "            list2 = list2.next\n",
    "        list2.next = t1 \n",
    "        return start.next\n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        fast, slow = list1, list1\n",
    "        k = b - a + 1\n",
    "        for _ in range(k):\n",
    "            fast = fast.next\n",
    "        for _ in range(a-1):\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        end = fast.next\n",
    "        pre, rear = list2, list2\n",
    "        while rear.next:\n",
    "            rear = rear.next\n",
    "        slow.next = pre\n",
    "        rear.next = end\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        pre = dummy = ListNode(-1)\n",
    "        pre.next = list1\n",
    "        prea  = pre\n",
    "        for i in range(a):\n",
    "            prea = prea.next\n",
    "        nodeb = list1    \n",
    "        for i in range(b):\n",
    "            nodeb = nodeb.next\n",
    "        prea.next = list2    \n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        cur.next = nodeb.next    \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        l = list1\n",
    "        for _ in range(a - 1):\n",
    "            l = l.next\n",
    "        r = l.next\n",
    "        for _ in range(b - a + 1):\n",
    "            r = r.next\n",
    "        l.next = list2\n",
    "        tail = list2\n",
    "        while tail.next: tail = tail.next\n",
    "        tail.next = r\n",
    "        \n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        prea = dummy = ListNode(0)\n",
    "        dummy.next = list1\n",
    "        nxb = None\n",
    "        b -= a\n",
    "        while a:\n",
    "            prea = prea.next\n",
    "            a -= 1\n",
    "        nxb = prea.next\n",
    "        while b:\n",
    "            nxb = nxb.next\n",
    "            b -= 1\n",
    "        nxb = nxb.next\n",
    "\n",
    "        head = list2\n",
    "        while head and head.next:\n",
    "            head = head.next\n",
    "\n",
    "        prea.next = list2\n",
    "        head.next = nxb\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        head = ListNode(0)\n",
    "        curr = head\n",
    "        i = 0\n",
    "        while i < a:\n",
    "            i += 1\n",
    "            curr.next = list1\n",
    "            list1 = list1.next\n",
    "            curr = curr.next\n",
    "        while i < b:\n",
    "            i += 1\n",
    "            list1 = list1.next\n",
    "        curr.next = list2\n",
    "        while curr.next:\n",
    "            curr = curr.next\n",
    "        curr.next = list1.next\n",
    "        return head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        hashmap1 = dict()\n",
    "        i = 0\n",
    "        node1 = list1\n",
    "        while node1:\n",
    "            hashmap1[i] = node1\n",
    "            i += 1\n",
    "            node1 = node1.next\n",
    "        hashmap1[a-1].next = list2\n",
    "        node2 = list2\n",
    "        while node2.next:\n",
    "            node2 = node2.next\n",
    "        node2.next = hashmap1.get(b+1, None)\n",
    "        hashmap1[b].next = None\n",
    "        return hashmap1[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        endnote = list1\n",
    "        count = -1\n",
    "        while endnote:\n",
    "            count += 1\n",
    "            if count == b:\n",
    "                endnote = endnote.next\n",
    "                break\n",
    "            endnote = endnote.next\n",
    "\n",
    "        cur2 = list2\n",
    "        while cur2:\n",
    "            if cur2.next == None:\n",
    "                cur2.next = endnote\n",
    "                break\n",
    "            cur2 = cur2.next\n",
    "\n",
    "        cur = list1\n",
    "        count = 0\n",
    "        while cur:\n",
    "            count += 1\n",
    "            if count == a:\n",
    "                cur.next = list2\n",
    "                break\n",
    "            cur = cur.next\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 432 ms ... 19.6 MB ... \n",
    "        #  time: O(n+m)\n",
    "        # space: O(n)\n",
    "        \n",
    "        idx2nod = {}\n",
    "        node = list1\n",
    "        index = 0\n",
    "        while node:\n",
    "            idx2nod[index] = node\n",
    "            index += 1\n",
    "            node = node.next\n",
    "        node = list2\n",
    "        while node.next:\n",
    "            node = node.next\n",
    "        idx2nod[a-1].next = list2\n",
    "        node.next = idx2nod[b+1]\n",
    "        return list1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        aa = []\n",
    "        tmp = list1\n",
    "        while tmp is not None:\n",
    "            aa.append(tmp.val)\n",
    "            tmp = tmp.next\n",
    "        def make(a):\n",
    "            ret = ListNode()\n",
    "            now = ret\n",
    "            for x in a:\n",
    "                tmp = ListNode(x)\n",
    "                now.next = tmp\n",
    "                now = tmp\n",
    "            return ret.next, now\n",
    "        a1,t1 = make(aa[:a])\n",
    "        a2,_ = make(aa[b+1:])\n",
    "        t1.next = list2\n",
    "        head = list2\n",
    "        while head.next is not None:\n",
    "            head = head.next\n",
    "        head.next=a2\n",
    "        return a1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0)\n",
    "        ans.next = list1\n",
    "        q = list2\n",
    "        while list2 and list2.next:\n",
    "            list2 = list2.next\n",
    "        count = 0\n",
    "        p = list1\n",
    "        while p:\n",
    "            count += 1\n",
    "            if count == a:\n",
    "                pre = p\n",
    "            p = p.next\n",
    "            if count == b+1:\n",
    "                break\n",
    "        pre.next = q\n",
    "        list2.next = p\n",
    "        return ans.next\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # dummy = ListNode(0)\n",
    "        # dummy.next = list1\n",
    "        # temp = dummy\n",
    "        temp = list1\n",
    "        for i in range(a-1):\n",
    "            temp = temp.next\n",
    "        prev = temp\n",
    "               \n",
    "        for j in range(b-a+2):\n",
    "            temp = temp.next\n",
    "        last = temp\n",
    "\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        prev.next = list2\n",
    "        cur.next = last\n",
    "\n",
    "        return list1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        length = 0\n",
    "        while list1:\n",
    "            if length == a - 1:\n",
    "                pre = list1\n",
    "            if length == b + 1:\n",
    "                nex = list1\n",
    "            length += 1\n",
    "            list1 = list1.next\n",
    "        pre.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = nex\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = list1\n",
    "        slow = fast = dummy\n",
    "        for _ in range(b-a+1):\n",
    "            fast = fast.next\n",
    "        for _ in range(a):\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        \n",
    "        tail_list2 = list2\n",
    "        while tail_list2.next:\n",
    "            tail_list2 = tail_list2.next\n",
    "\n",
    "        slow.next = list2\n",
    "        tail_list2.next = fast.next\n",
    "        fast.next = None\n",
    "\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur1 = list1\n",
    "        cur2 = list2\n",
    "        prev = prev1 = ListNode()\n",
    "        \n",
    "        n = 0\n",
    "        while cur1:\n",
    "            if n < a:\n",
    "                prev1.next = cur1\n",
    "                prev1 = prev1.next\n",
    "                cur1 = cur1.next\n",
    "           \n",
    "            elif a <= n < b:\n",
    "                cur1 = cur1.next\n",
    "            elif n == b:\n",
    "                cur1 = cur1.next\n",
    "                while cur2:\n",
    "                   prev1.next = cur2\n",
    "                   prev1 = prev1.next\n",
    "                   cur2 = cur2.next\n",
    "      \n",
    "            elif n > a:\n",
    "\n",
    "                prev1.next = cur1\n",
    "                prev1 = prev1.next\n",
    "                cur1 = cur1.next\n",
    "            n = n + 1\n",
    "        return prev.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # 连接list2尾部和b+1个节点\n",
    "        L1 = list1\n",
    "        L2 = list2\n",
    "        while L2.next:\n",
    "            L2 = L2.next\n",
    "        while b >= 0:\n",
    "            L1 = L1.next\n",
    "            b -= 1\n",
    "        L2.next = L1\n",
    "\n",
    "        # 连接list2头部\n",
    "        # 这里用哑结点更方便一点\n",
    "        L1 = ListNode(-1, list1)\n",
    "        while a > 0:\n",
    "            L1 = L1.next\n",
    "            a -= 1\n",
    "        L1.next = list2\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        if not list1:\n",
    "            return list1\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = list1\n",
    "        # 找到a-1节点\n",
    "        nodeA = list1\n",
    "        for i in range(a-1):\n",
    "            nodeA = nodeA.next\n",
    "        # 找到b+1节点\n",
    "        nodeB = nodeA\n",
    "        for i in range(a-1, b+1):\n",
    "            nodeB = nodeB.next\n",
    "\n",
    "        # 找到list2的尾节点\n",
    "        tail = list2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "        # 把list2接入到list1的a，b位置\n",
    "        tail.next = nodeB\n",
    "        nodeA.next = list2\n",
    "\n",
    "        return dummy.next\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        point = res = ListNode(0)\n",
    "        res.next = list1\n",
    "        res = res.next\n",
    "        for i in range(a-1):\n",
    "            list1 = list1.next\n",
    "        tmp = list1.next\n",
    "        for i in range(b-a):\n",
    "            tmp = tmp.next\n",
    "        list1.next = list2\n",
    "        while list1.next:\n",
    "            list1 = list1.next\n",
    "        list1.next = tmp.next\n",
    "        return point.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        pA = list1\n",
    "        for i in range(a-1):\n",
    "            pA = pA.next\n",
    "        pB = pA\n",
    "        for i in range(b-a+1):\n",
    "            pB = pB.next\n",
    "        pA.next = list2\n",
    "        p = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = pB.next\n",
    "        return list1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1, list1)\n",
    "        curA = dummy\n",
    "        tmp = list1\n",
    "        # 找到b, 标记b+1\n",
    "        for _ in range(b):\n",
    "            tmp = tmp.next\n",
    "        curB = tmp.next\n",
    "        tmp.next = None\n",
    "\n",
    "        # 找到a, 标记a-1\n",
    "        for _ in range(a):\n",
    "            curA = curA.next\n",
    "        curA.next = None\n",
    "\n",
    "        # 遍历list2, 标记尾节点tail\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        \n",
    "        # 整合链表\n",
    "        curA.next = list2\n",
    "        cur.next = curB\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p1, p2 = list1, list1\n",
    "        while a > 1:\n",
    "            p1 = p1.next\n",
    "            a -= 1\n",
    "        while b > -1:\n",
    "            p2 = p2.next\n",
    "            b -= 1\n",
    "        \n",
    "        tail = list2\n",
    "        while tail.next:\n",
    "            tail = tail.next\n",
    "\n",
    "        p1.next = list2\n",
    "        tail.next = p2\n",
    "\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "          因为a>=1,所以不会删除第一个节点\n",
    "        \"\"\"\n",
    "        node_num = 0\n",
    "        cur = list1\n",
    "        while cur and node_num<a-1:\n",
    "            cur = cur.next\n",
    "            node_num += 1\n",
    "        cur1 = cur\n",
    "        while cur1 and node_num<=b:\n",
    "            cur1 = cur1.next\n",
    "            node_num += 1\n",
    "        cur.next = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        cur.next = cur1\n",
    "        return list1\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ind = 0\n",
    "        p = list1\n",
    "        while p:\n",
    "            if ind == a-1:start = p\n",
    "            if ind == b+1:end = p\n",
    "            p = p.next\n",
    "            ind = ind+1\n",
    "        start.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = end\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        offseta = a\n",
    "        offsetb = b\n",
    "        offset = max(a, b)\n",
    "        a = b = None\n",
    "\n",
    "        a_pre = None\n",
    "        cur = list1\n",
    "        offseti = 0\n",
    "        while cur and offseti <= offset:\n",
    "            if offseti == offseta-1:\n",
    "                a_pre = cur\n",
    "            if offseti == offsetb:\n",
    "                b = cur\n",
    "\n",
    "            offseti += 1\n",
    "            cur = cur.next\n",
    "\n",
    "        tail2 = list2\n",
    "        while tail2 and tail2.next:\n",
    "            tail2 = tail2.next\n",
    "\n",
    "        if not a_pre and not b:\n",
    "            return list2\n",
    "\n",
    "        if not a_pre and b:\n",
    "            if tail2:\n",
    "                tail2.next = b.next\n",
    "            if not list2:\n",
    "                return b.next\n",
    "            return list2\n",
    "\n",
    "        if a_pre and not b:\n",
    "            a_pre.next = None\n",
    "            a_pre.next = list2\n",
    "            return list1\n",
    "\n",
    "        if a_pre and b:\n",
    "            if not list2:\n",
    "                a_pre.next = b.next\n",
    "            else:\n",
    "                a_pre.next = list2\n",
    "                tail2.next = b.next\n",
    "            return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        for _ in range(a-1):\n",
    "            node = node.next\n",
    "        part3_node = node\n",
    "        for _ in range(b-a+2):\n",
    "            part3_node = part3_node.next\n",
    "        node2 = list2\n",
    "        while node2.next:\n",
    "            node2 = node2.next\n",
    "        node.next = list2\n",
    "        node2.next = part3_node\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(-1, list1)\n",
    "        curr = dummy\n",
    "        start = 0\n",
    "        while list1:\n",
    "            if start == a:\n",
    "                while list2:\n",
    "                    curr.next = list2\n",
    "                    list2 = list2.next\n",
    "                    curr = curr.next\n",
    "            while start >= a and start <= b:\n",
    "                list1 = list1.next\n",
    "                start += 1\n",
    "            start += 1\n",
    "            curr.next = list1\n",
    "            curr = curr.next\n",
    "            list1 = list1.next\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):\n",
    "            p=p.next\n",
    "        for _ in range(b):\n",
    "            q=q.next\n",
    "        p.next=list2\n",
    "        while p.next:\n",
    "            p=p.next\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur_node = list1\n",
    "        c = 0\n",
    "        while cur_node:\n",
    "            if c == a - 1:\n",
    "                st_node = cur_node\n",
    "            if c == b + 1:\n",
    "                ed_node = cur_node\n",
    "            cur_node = cur_node.next\n",
    "            c += 1\n",
    "        \n",
    "        cur_node = list1\n",
    "        while cur_node:\n",
    "            if cur_node == st_node:\n",
    "                cur_node.next = list2\n",
    "                while list2.next:\n",
    "                    list2 = list2.next\n",
    "                list2.next = ed_node\n",
    "                cur_node = ed_node\n",
    "            cur_node = cur_node.next\n",
    "        \n",
    "        return list1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # dummy_node = ListNode()\n",
    "        # dummy_node.next = list1\n",
    "        # while \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):p=p.next#遍历到a\n",
    "        for _ in range(b):q=q.next#找到b+1\n",
    "        p.next=list2\n",
    "        while p.next:\n",
    "            p=p.next\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p=q=list1\n",
    "        for _ in range(a-1):p=p.next#遍历到a-1节点\n",
    "        for _ in range(b):q=q.next#找到b\n",
    "        p.next=list2 #a-1指向Liste2\n",
    "        while p.next:\n",
    "            p=p.next #遍历到末尾\n",
    "        p.next=q.next\n",
    "        q.next=None\n",
    "        return list1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p,q = list1,list1\n",
    "        for i in range(a-1):\n",
    "            p = p.next\n",
    "        for i in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        # 需要寻找a的前缀和b的next\n",
    "        protect = list1\n",
    "        list1_index = 1\n",
    "        while list1.next:\n",
    "            if list1_index == a:\n",
    "                # 记录下来a节点的前缀位置\n",
    "                flag_a_prior = list1\n",
    "            if list1_index == b:\n",
    "                # 记录下来b节点的next位置\n",
    "                flag_b_next = list1.next.next\n",
    "            list1 = list1.next\n",
    "            list1_index += 1\n",
    "        # 把list2拼接在a的前缀的next\n",
    "        flag_a_prior.next = list2\n",
    "        # 找到list2的尾指针\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        # 把b的next拼接在list2尾指针的位置\n",
    "        list2.next = flag_b_next\n",
    "        return protect\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur=list1\n",
    "        for i in range(a-1):\n",
    "            cur=cur.next\n",
    "        aft=list1\n",
    "        for i in range(b):\n",
    "            aft=aft.next\n",
    "        cur.next=list2\n",
    "        while cur.next:\n",
    "            cur=cur.next\n",
    "        cur.next=aft.next\n",
    "        aft.next=None\n",
    "        return list1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        preA = list1\n",
    "        for _ in range(a - 1):\n",
    "            preA = preA.next\n",
    "        preB = preA\n",
    "        for _ in range(b - a + 2):\n",
    "            preB = preB.next\n",
    "        preA.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        list2.next = preB\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p,q = list1,list1\n",
    "        for i in range(a-1):\n",
    "            p = p.next\n",
    "        for i in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        site=0\n",
    "        site2=0\n",
    "        len2=0\n",
    "        cur1=list1\n",
    "        cur2=list2\n",
    "        while cur2:\n",
    "            len2+=1\n",
    "            cur2=cur2.next\n",
    "        while cur1:\n",
    "            site2+=1\n",
    "            cur1=cur1.next\n",
    "            if site2==b:\n",
    "                end=cur1.next\n",
    "                break\n",
    "        cur1=list1\n",
    "        while cur1:\n",
    "            site+=1\n",
    "            if site==a:\n",
    "                cur1.next=list2\n",
    "                while cur1.next:\n",
    "                    cur1=cur1.next\n",
    "                    site+=1\n",
    "                cur1.next=end\n",
    "                break\n",
    "            cur1=cur1.next\n",
    "        return list1\n",
    "\n",
    "    \n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        def find(h, pos):\n",
    "            now = h\n",
    "            if pos == -1:\n",
    "                while now.next:\n",
    "                    now = now.next\n",
    "            else:\n",
    "                for i in range(pos):\n",
    "                    now = now.next\n",
    "            return now\n",
    "\n",
    "        pre = find(list1, a - 1)\n",
    "        tail = find(list1, b + 1)\n",
    "        pre.next =  list2\n",
    "        find(list2, -1).next = tail\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "\n",
    "        # 获取索引为a-1的节点\n",
    "        aprev = list1\n",
    "        for _ in range(a-1):\n",
    "            aprev = aprev.next\n",
    "        \n",
    "        # 获取索引为b+1的节点\n",
    "        bnext = aprev\n",
    "        for _ in range(b-a+2):\n",
    "            bnext = bnext.next\n",
    "\n",
    "        # 合并\n",
    "        aprev.next = list2\n",
    "        while aprev.next:\n",
    "            aprev = aprev.next\n",
    "        aprev.next = bnext\n",
    "\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur=list1\n",
    "        i=0\n",
    "        while cur:\n",
    "            if i==a-1:\n",
    "                node1=cur\n",
    "            elif i==b:\n",
    "                node2=cur\n",
    "                break\n",
    "            i+=1\n",
    "            cur=cur.next\n",
    "        node1.next=list2\n",
    "        while list2.next:\n",
    "            list2=list2.next\n",
    "        list2.next=node2.next\n",
    "        node2.next=None\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur = 0\n",
    "        left = list1\n",
    "        pre = None\n",
    "        while cur!=a:\n",
    "            pre = left\n",
    "            left = left.next\n",
    "            cur+=1\n",
    "        right = left\n",
    "        while cur!=b:\n",
    "            right = right.next\n",
    "            cur+=1\n",
    "        ans = None\n",
    "        cur = list2\n",
    "        while cur.next is not None:\n",
    "            cur = cur.next\n",
    "        cur.next = right.next\n",
    "        if pre is None:\n",
    "            ans = list2\n",
    "        else:\n",
    "            ans = list1\n",
    "            pre.next = list2\n",
    "            cur = list2\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p = q = list1\n",
    "        for _ in range(a-1):\n",
    "            p = p.next\n",
    "        for _ in range(b):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        q.next = None\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        index = 0\n",
    "        pivot = list1\n",
    "        while index < a-1:\n",
    "            pivot = pivot.next\n",
    "            index += 1\n",
    "        left = pivot\n",
    "        while index <= b:\n",
    "            pivot = pivot.next\n",
    "            index +=1\n",
    "        right = pivot\n",
    "        left.next = list2\n",
    "        pivot = list2\n",
    "        while pivot.next!=None:\n",
    "            pivot = pivot.next\n",
    "        pivot.next = right\n",
    "        return list1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        lenth = 0\n",
    "        cur = list1\n",
    "        before_a = after_b = list1\n",
    "        for _ in range(a-1):\n",
    "            before_a = before_a.next\n",
    "        \n",
    "        for _ in range(b+1):\n",
    "            after_b = after_b.next\n",
    "        \n",
    "        before_a.next = list2\n",
    "        while before_a.next:\n",
    "            before_a = before_a.next\n",
    "        before_a.next = after_b\n",
    "\n",
    "        return list1\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        p = q = list1\n",
    "        for _ in range(a - 1):\n",
    "            p = p.next\n",
    "        for _ in range(b):\n",
    "            q = q.next\n",
    "        # print(p.val,q.val)\n",
    "        p.next = list2\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        p.next = q.next\n",
    "        # print(list1)\n",
    "        # q.next = None\n",
    "        return list1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        lenth = 0\n",
    "        cur = cur_a = cur_b = list1\n",
    "        before_a = after_b = list1\n",
    "        while cur:\n",
    "            lenth += 1\n",
    "            if lenth == a:\n",
    "                before_a = cur\n",
    "            if lenth == b+1:\n",
    "                after_b = cur.next\n",
    "                cur.next = None\n",
    "                before_a.next = None\n",
    "                break\n",
    "            cur = cur.next\n",
    "\n",
    "        # list2的结尾\n",
    "        cur = list2\n",
    "        while cur.next:\n",
    "            cur = cur.next\n",
    "        before_a.next, cur.next = list2, after_b\n",
    "\n",
    "        return list1\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cache1 = []\n",
    "        cache2 = []\n",
    "        while list1:\n",
    "            cache1.append(list1)\n",
    "            list1 = list1.next\n",
    "        while list2:\n",
    "            cache2.append(list2)\n",
    "            list2 = list2.next\n",
    "        cache2[-1].next = cache1[b+1] if b+1<len(cache1) else None\n",
    "        if a-1>=0:\n",
    "            cache1[a-1].next = cache2[0]\n",
    "            return cache1[0]\n",
    "        else:\n",
    "            return cache2[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0, list1)\n",
    "        temp = ans\n",
    "        flag = 0\n",
    "        while flag < a:\n",
    "            flag += 1\n",
    "            temp = temp.next\n",
    "        temp2 = temp\n",
    "        while flag <= b:\n",
    "            temp2 = temp2.next\n",
    "            flag += 1\n",
    "        temp.next = list2\n",
    "        while temp.next:\n",
    "            temp = temp.next\n",
    "        temp.next = temp2.next\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        head = list1 \n",
    "        for _ in range(1, a):\n",
    "            list1 = list1.next \n",
    "        start = list1 \n",
    "        for _ in range(a, b+2):\n",
    "            list1 = list1.next\n",
    "        end = list1 \n",
    "        start.next = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next \n",
    "        list2.next = end\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        node = list1\n",
    "        for _ in range(a - 1):\n",
    "            node = node.next\n",
    "        middle = node.next.next\n",
    "        node.next = list2\n",
    "\n",
    "        # 找到切断后右边最左的节点\n",
    "        for _ in range(b - a):\n",
    "            middle = middle.next\n",
    "        \n",
    "\n",
    "        # 找到list2的尾部\n",
    "        list2 = list2\n",
    "        while list2.next:\n",
    "            list2 = list2.next\n",
    "        \n",
    "        list2.next = middle\n",
    "        return list1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\r\n",
    "            \r\n",
    "            dummy = ListNode(0)\r\n",
    "            dummy.next = list1\r\n",
    "            pre = dummy\r\n",
    "            cur = list1\r\n",
    "            for _ in range(a):\r\n",
    "                pre = cur\r\n",
    "                cur = cur.next\r\n",
    "            pre.next = list2\r\n",
    "            while list2.next:\r\n",
    "                list2 = list2.next\r\n",
    "            for _ in range(b-a+1):\r\n",
    "                cur = cur.next\r\n",
    "            list2.next = cur\r\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        cur1=list1\n",
    "        i=0\n",
    "        while i<a-1:\n",
    "            cur1=cur1.next\n",
    "            i+=1\n",
    "        cur2=cur1.next\n",
    "        cur1.next=list2\n",
    "        while cur1.next!=None:\n",
    "            cur1=cur1.next\n",
    "\n",
    "        while i<b:\n",
    "            cur2=cur2.next\n",
    "            i+=1\n",
    "        cur1.next=cur2\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:\n",
    "        dummy = p = q = ListNode(0, list1)\n",
    "        for i in range(a):\n",
    "            p = p.next\n",
    "        for i in range(b + 2):\n",
    "            q = q.next\n",
    "        p.next = list2\n",
    "        p = list2\n",
    "        while p.next != None:\n",
    "            p = p.next\n",
    "        p.next = q\n",
    "        return dummy.next\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
